/**
 * @Project : algorithm-learning
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/3/24 15:54
 */

//多多有一个长度为n的字符串,这个字符串由26个小写字母组成.
//多多可以对这个字符串进行多次操作,每次操作可以把该字符串中一段连续的回文子串删除(单个字符也属于回文串),删除后剩下的串会拼在一起.
//请问最少需要多少次操作可以将这个字符串删光。
//
//输入描述
//  第一行,包含一个正整数T(1≤T≤20)代表测试数据的组数.
//  对于每组测试数据,仅有一行,代表这个字符串.
//  (1≤n≤500) 保证\sumn不超过3000
//输出描述
//  对于每组数据输出一行整数,代表多多在进行最少多少次操作后,可以将这个字符串删光.
//
//示例1
//输入
//3
//mwapd
//tvuvv
//yxxmi
//输出
//5
//3
//4
//说明
//  对于tvuvv
//  第一步:删除u,此时剩下tvvv
//  第二步:删除vvv,此时剩下t
//  第三步:删除t

#include <iostream>

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    for (int m = 0; m < t; ++m) {
        string s;
        cin >> s;
        int f[s.length()][s.length()];
        for (int i = 0; i < s.length(); ++i) {
            for (int j = 0; j < s.length(); ++j) {
                if (i != j)f[i][j] = 0;
                else f[i][j] = 1;
            }
        }
        for (int len = 2; len <= s.length(); ++len) {
            for (int i = 0, j = i + len - 1; j < s.length(); ++i, ++j) {
                f[i][j] = 0x3f3f3f3f;
                if (s[i] == s[i + 1]) f[i][j] = min(f[i][j], f[i + 1][j]);
                else f[i][j] = min(f[i][j], f[i + 1][j] + 1);
                if (s[j] == s[j - 1]) f[i][j] = min(f[i][j], f[i][j - 1]);
                else f[i][j] = min(f[i][j], f[i + 1][j] + 1);
                if (s[i] == s[j]) f[i][j] = min(f[i][j], f[i + 1][j - 1] + 1);
                else f[i][j] = min(f[i][j], f[i + 1][j - 1] + 2);
            }
        }
//        for (int i = 0; i < s.length(); ++i) {
//            for (int j = 0; j < s.length(); ++j) {
//                cout << f[i][j] << " ";
//            }
//            cout << endl;
//        }
//        cout << endl;
        printf("%d\n", f[0][s.length() - 1]);
    }
    return 0;
}